A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Network devices exchange packets in packet flows during network sessions. Typically, one network device establishes a network session, also referred to as a communication session, with another network device. Each of the two network devices transmits packets of the network session in a respective packet flow to the other network device. In general, a network session corresponds to two packet flows, one packet flow in either direction between the two network devices participating in the network session. In some examples, a network session corresponds to multiple packet flows, with one or more packet flows in either direction between network devices participating in the network session.
In some cases, intermediate devices store packet flow state information and/or network session state information, e.g., when monitoring the packet flows and/or network sessions. For example, many network security devices such as intrusion detection and prevention devices (IDP devices) and firewall devices, monitor packet flow state information to determine whether a network device participating in a communication session is exhibiting signs of malicious behavior. As another example, application acceleration systems monitor packet flow state information to add a new packet flow, close an existing packet flow, or decide to which flow a received packet belongs. Common Internet File System (CIFS) acceleration, as another example, accesses session state information to determine whether a file block has been cached locally.
Many devices, such as cellular telephones and other mobile devices, are becoming Internet-capable, and more consumers are connecting to the Internet on a regular basis. Accordingly, the burden on intermediate network devices that monitor packet flow state information is increasing. Some intermediate network devices, for example, are tasked with monitoring tens of million packet flows. One example data structure for storing flow state information for one packet flow occupies hundreds of bytes or even multiple kilobytes. Intermediate devices commonly store such data structures as entries in a flow table, where there are entries for each monitored packet flow. Thus to successfully monitor all of the packet flows, an intermediate device uses a tremendous amount of memory, which in turn diverts processing resources to performing memory management.